package ljl.codetop300;

import commons.ListNode;

import java.util.List;

/**
 * 这个题有几个点要注意：
 *   从第三个开始
 *   最后要把偶数节点的 next 置空，不然就错了
 */
public class _328_odd_even_list {

  /**
   * 双指针一趟不完了吗？
   */
  static class test {
    public ListNode oddEvenList(ListNode head) {
      if (head == null || head.next == null) return head;
      ListNode pOdd = head;
      ListNode even = head.next;
      ListNode pEven = even;
      ListNode p = even.next;
      int i = 3;
      while (p != null) {
        ListNode next = p;
        if (i % 2 == 1) {
          pOdd.next = next;
          pOdd = next;
        } else {
          pEven.next = next;
          pEven = next;
        }
        p = p.next;
        i++;
      }
      pEven.next = null;
      pOdd.next = even;
      return head;
    }
  }

  /**
   * 它的好，更简短
   */
  static class off {
    // odd even even.next
    public ListNode oddEvenList(ListNode head) {
      if (head == null) return null;
      ListNode evenHead = head.next;
      ListNode odd = head, even = evenHead;
      // 只有 even.next 不为 null 才有必要继续往下走
      while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
      }
      odd.next = evenHead;
      return head;
    }
  }

  static class copy_off {
    /**
     * 自作聪明。head.next 是不变的吗？
     */
    public ListNode oddEvenList(ListNode head) {
      if (head == null || head.next == null) return head;
      ListNode evenHead = head.next;
      ListNode peven = evenHead;
      ListNode podd = head;
      while (peven != null && peven.next != null) {
        podd.next = peven.next;
        podd = podd.next;
        peven.next = podd.next;
        peven = peven.next;
      }
      podd.next = evenHead;
      return head;
    }

  }
}
